package org.lql.algo.codecrush.hot100.array;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 21:49
 * @description: 53. 最大子数组和 <a href="https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class MaxSubArray {

	public int maxSubArray(int[] nums) {
		int n = nums.length;
		int[] f = new int[n];
		f[0] = nums[0];
		for (int i = 1; i < n; i++) {
			f[i] = Math.max(f[i - 1], 0) + nums[i];
		}
		int ans = f[0];
		for (int i = 1; i < n; i++) {
			ans = Math.max(ans, f[i]);
		}
		return ans;
	}


	public static void main(String[] args) {
		// 6
		System.out.println(new MaxSubArray().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
		// 1
		System.out.println(new MaxSubArray().maxSubArray(new int[]{1}));
		// 23
		System.out.println(new MaxSubArray().maxSubArray(new int[]{5, 4, -1, 7, 8}));
		// 1
		System.out.println(new MaxSubArray().maxSubArray(new int[]{-2, 1}));
	}
}
